As background for our invention the present application relates to computer systems, which have an execution unit or processor known as a central processing unit or CPU, a main memory and a cache system. The cache is a memory which functions as a small fast barrier that is placed between the CPU and main memory to provide the functionality of the main memory at the speed of the CPU.
The first commercially successful system which employed a cache was the IBM 360/85, a 1969 mainframe system. Since then many system employ a cache, and today, personal computers and workstations have a cache. However, while it has been recognized that a cache may increase the overall system performance by reducing or eliminating processor wait states during memory access, caches are noticeably absent in real time systems which have real or hard deadlines which must be matched to effectively perform the required tasks.
Prior cache designs result in unpredictable performance improvements and therefor are not used or are disabled so they can not be utilized in "hard" real-time systems. Real-time system require predicable execution time in order to guarantee that the hard deadlines are met. Cache memories, while providing significant performance improvements over conventional memory designs, result in unpredictable execution times when exposed to task preemptions and interrupts and cache cold starts. As a result generally real time systems currently are trending toward algorithmic scheduling, as I discussed in my presentation on "Process Dependent Static Cache Partitioning for Real Time Systems", Proceedings of the Read-Time Systems Symposium, pp 181-190, Huntsville, Ala., December 1988.
Others might approach the problem with multiple, bank switched, caches or some method of unloading the contents of a cache, as part of a task swap out, then reloading the cache when the task is swapped in, these other approaches would be more expensive and slower than desirable.
The patent art includes a quite a number of patents dealing with cache memory organizations. U.S. Pat. 4,442,487 to Fletcher et al, issued Apr. 10, 1984 for instance, deals with a multi-processing memory for a processor, and how processors can share cache, not how multi-tasks can share cache. U.S. Pat. 5,025,366 to Baror, issued Jun. 18,1991 is a recent example of how cache can be employed on a single chip, and U.S. Pat. 4,997,498 issued Dec. 11, 1990 deals with a data processing system having a data memory interlock, as an example of line lock. The current improvements can be employed whether or not the cache is located on the chip, or externally. The line locking used by the cache memory need not be used with the current improvements, but it could be.
It also has been recognized by the general references which are discussed as general background (Thiebaut, Stone and Wolf, An internal IBM Technical Report entitled A Theory of Cache Behavior) that a computer system can have a cache which is partitioned for data and instruction to optimize cache performance, which does not handle predictability. A computer called ELXSI System 6400 has been also generally discussed. This computer is targeted for real time systems and provides partitioning. However, the dynamic allocation of these partitions prevents cache predictability.
Within International Business Machines it has been suggested, as illustrated by European Patent Application Publication No.0 391 871 published Oct. 10, 1990 on application 90850122.4, by Kevin Smith that one could within hardware dynamically allocate cache size based on a data structure. This patent is directed to a way of optimize performance, not to achieve the predictability of real-time requirements. IBM Technical Disclosure Bulletin Vo. 32. No. 8B, of January 1990 by K. Kawachiya et al, entitled Memory Management Mechanism to Reduce Cache-Line Contention, suggested partitioning a cache into functional areas to avoid contention. They suggest address mapping as a method of partitioning. Once again, this does not provide the necessary predictability.
Generally, systems which are designed for real-time applications could benefit from cache performance improvements if the effects of interrupts and preemptions can be overcome to provide a predictable cache operation.